《数据结构》第一学期期末试卷A (精选01)

试卷信息：满分 100 分 | 考试时间 120 分钟 | 难度分布：基础 40% · 中等 40% · 提高 20%

一、判断题（每题 2 分，共 10 分）（正确的打"√"，错误的打"×"。）

广义表通常采用顺序存储结构。（）

查看答案与解析

答案：×

解析：
广义表是一种非线性的数据结构，其元素可以是原子，也可以是另一个广义表（子表）。由于广义表的结构复杂、规模多变，采用顺序存储难以应对动态变化和不同长度的子表，因此通常采用链式存储结构（如头尾链表表示法或同构型表示法）来实现。

难度: ⭐
考点: #广义表 #存储结构

💡 学习锦囊

📖 相关公式与知识点:

广义表是 $n \ge 0$ 个表元素 $\alpha_1, \alpha_2, \dots, \alpha_n$ 的有限序列。
广义表的深度：表中所含括号的最大层数。

思路分析

判断数据结构的存储方式时，需结合其逻辑特性的动态性。广义表由于支持嵌套和动态扩展，链式存储是更自然的选择。

易错点

误以为所有“表”结构都默认采用顺序存储。

🔄 举一反三

广义表 $$L = (a, (b, c))$$ 的深度是多少？
查看练习答案与解析
答案：2
解析：嵌套的最大括号层数为 2（元素 $$(b, c)$$ 在第二层），故深度为 2。

邻接表适用于稀疏图，而邻接矩阵适用于稠密图。（）

查看答案与解析

答案：√

解析：

邻接矩阵的存储空间固定为 $$O(n^2)$$ ，与边数无关，适合边数较多的稠密图。
邻接表的存储空间为 $$O(n + e)$$ ，与边数直接相关。在边数较少的稀疏图中，邻接表能显著节省空间。

难度: ⭐
考点: #图 #邻接矩阵 #邻接表

💡 学习锦囊

📖 相关公式与知识点:

稀疏图条件： $e \ll n(n-1)$ 。

思路分析

从空间复杂度的角度对比两种存储结构。稀疏图边少，使用邻接矩阵会造成大量 0 的浪费。

易错点

混淆稀疏图和稠密图的空间优势。

🔄 举一反三

一个具有 $$n$$ 个顶点的无向图，采用邻接表表示时，表结点的总数是多少？
查看练习答案与解析
答案： $$2e$$ （ $$e$$ 为边数）
解析：无向图中每条边 $$(u, v)$$ 会在顶点 $$u$$ 和 $$v$$ 的邻接表中各生成一个结点。

线性表的链式存储结构的特点是，用一组任意的存储单元存储线性表的数据元素，这组存储单元可以是连续的，也可以是不连续的。（）

查看答案与解析

答案：√

解析：
链式存储结构不要求逻辑上相邻的元素在物理位置上也相邻。它通过指针来表示元素之间的逻辑关系，因此存储单元可以是任意的、连续或不连续的。

难度: ⭐
考点: #线性表 #链式存储

💡 学习锦囊

📖 相关公式与知识点:

链表特点：顺序存取，插入删除不需要移动元素。

思路分析

牢记链表的基本定义——依靠指针而非物理相邻来维护逻辑顺序。

易错点

误以为链表绝对不能占用连续的物理空间（其实可以是连续的，只是不要求）。

🔄 举一反三

顺序存储结构的主要缺点是什么？
查看练习答案与解析
答案：插入和删除需要移动大量元素；需要预先分配连续空间。
解析：顺序表为了保持物理连续性，在中间操作时必须移动后续元素。

数据结构中，栈具有先进先出特性，队列具有后进先出特性。（）

查看答案与解析

答案：×

解析：
概念记反了。**栈（Stack）**是后进先出（LIFO）；**队列（Queue）**是先进先出（FIFO）。

难度: ⭐
考点: #栈 #队列

💡 学习锦囊

📖 相关公式与知识点:

栈：操作受限在表尾（栈顶）。
队列：操作受限在表头和表尾。

思路分析

这是数据结构中最基础的两个受限线性表，必须牢记其存取规则。

易错点

基础概念混淆。

🔄 举一反三

哪些算法常借用栈来实现？
查看练习答案与解析
答案：深度优先搜索（DFS）、括号匹配、表达式求值等。
解析：这些算法都需要保存当前状态并在之后回溯（后进先出）。

完全二叉树的一个结点若无右孩子，则此结点必为叶子结点。（）

查看答案与解析

答案：×

解析：
在完全二叉树中，结点的排列是有序的。一个结点若无右孩子，它可能有一个左孩子（此时该结点度为 1，属于分支结点）。

难度: ⭐⭐
考点: #完全二叉树

💡 学习锦囊

📖 相关公式与知识点:

完全二叉树性质：除了最后一层外，其余各层都是满的，且最后一层的结点都连续集中在左边。

思路分析

画出最典型的反例：一个只有左孩子、没有右孩子的结点。

易错点

忽略了度为 1 的结点的存在。

🔄 举一反三

具有 10 个结点的完全二叉树中，度为 1 的结点个数是多少？
查看练习答案与解析
答案：1
解析：根据完全二叉树的结构特点，当结点总数为偶数时，必然存在一个度为 1 的结点。

二、单选题（每题 2 分，共 30 分）

从逻辑结构上可将数据结构分为（）。
- A．静态结构和动态结构
- B. 紧凑结构和非紧凑结构
- C. 内部结构和外部结构
- D. 线性结构和非线性结构

查看答案与解析

答案：D

解析：
数据结构在逻辑上分为两大类：线性结构（如线性表、栈、队列）和非线性结构（如树、图）。静态/动态、紧凑/非紧凑通常属于物理存储或管理范畴。

难度: ⭐
考点: #逻辑结构

💡 学习锦囊

📖 相关公式与知识点:

逻辑结构：数据元素之间的逻辑关系，与存储无关。

思路分析

理清逻辑结构与存储结构的区别。

易错点

混淆逻辑分类与存储分类。

🔄 举一反三

顺序表和链表属于什么结构的分类？
查看练习答案与解析
答案：存储结构（物理结构）。
解析：它们是线性结构在计算机中的不同具体实现方式。

算法分析的目的是（）。
- A. 找出数据结构的合理性
- B. 研究算法中的输入和输出的关系
- C. 分析算法的效率以求改进
- D. 分析算法的可读性和简明性

查看答案与解析

答案：C

解析：
算法分析的核心是对算法的时间复杂度和空间复杂度进行评估，目的是分析算法的效率，从而选择最优解或进行改进。

难度: ⭐
考点: #算法分析

💡 学习锦囊

📖 相关公式与知识点:

算法的五个特性：有穷性、确定性、可行性、输入、输出。

思路分析

分析算法不是为了看它能不能跑，而是看它跑得快不快、省不省内存。

易错点

误选 D（可读性虽然重要，但不是分析的主要目的）。

🔄 举一反三

算法的时间复杂度取决于什么？
查看练习答案与解析
答案：问题的规模和待处理数据的初始状态。
解析：例如排序算法，最好和最坏情况下的时间代价往往不同。

在单链表上实现删除和插入操作（）。
- A. 不需要移动结点，不需要改变结点指针
- B. 不需要移动结点，只需要改变结点指针
- C. 只需移动结点，不需要改变结点指针
- D. 既需移动结点，又需要改变结点指针

查看答案与解析

答案：B

解析：
链表通过指针连接。在单链表中插入或删除结点，只需要修改相关结点的 next 指针即可，物理位置不需要移动。

难度: ⭐
考点: #单链表 #插入删除

💡 学习锦囊

📖 相关公式与知识点:

插入操作：s->next = p->next; p->next = s;
删除操作：p->next = q->next; free(q);

思路分析

对比顺序表，顺序表需要移动元素，链表只需要修改指针。

易错点

修改指针的顺序不能颠倒，否则会导致链表断裂。

🔄 举一反三

在双向链表中插入结点的指针修改次数通常是多少？
查看练习答案与解析
答案：4 次。
解析：需要修改新结点的两个指针，以及前后结点的各一个指针。

假设一个栈的输入序列是 1，2，3，4，则不可能得到的输出序列是（）。
- A．1，2，3，4
- B．4，1，2，3
- C．4，3，2，1
- D．1，3，4，2

查看答案与解析

答案：B

解析：

A：1入1出，2入2出，3入3出，4入4出 -> 1,2,3,4。
C：1,2,3,4全入，再依次出 -> 4,3,2,1。
D：1入出，2入，3入出，4入出，2出 -> 1,3,4,2。
B：若第一个出栈的是 4，说明 1,2,3 已在栈中。此时栈顶是 3，下一个出栈的必须是 3，绝对不可能是 1。

难度: ⭐⭐
考点: #栈 #输出序列

💡 学习锦囊

📖 相关公式与知识点:

栈的后进先出特性。

思路分析

逐项模拟入栈出栈过程。

易错点

看到 4 第一个出，就盲目认为后面的数字可以任意排列。

🔄 举一反三

栈输入序列为 A, B, C，可能的输出序列有多少种？
查看练习答案与解析
答案：5 种。
解析：利用卡特兰数公式 $C_n = \frac{1}{n+1}\binom{2n}{n}$ ，当 $$n=3$$ 时， $$C_3 = 5$$ 。

为解决计算机主机与打印机之间速度不匹配的问题，通常设置一个打印数据缓冲区。主要将要输出的数据依次写入该缓冲区，而打印机则依次从该缓冲区中取出数据。该缓冲区的逻辑结果应该是（）。
- A. 栈
- B. 队列
- C. 树
- D. 图

查看答案与解析

答案：B

解析：
数据写入缓冲区和取出打印遵循“先来先服务”的原则，即先存入的数据先打印，这完全符合队列先进先出（FIFO）的特性。

难度: ⭐
考点: #队列应用

💡 学习锦囊

📖 相关公式与知识点:

队列的应用场景：资源分配、消息缓冲、广度优先搜索。

思路分析

抓住“依次写入”和“依次取出”的先后顺序逻辑。

易错点

误选为栈（栈常用于回溯、递归）。

🔄 举一反三

操作系统中的进程调度，就绪队列采用什么数据结构？
查看练习答案与解析
答案：队列。
解析：保证先就绪的进程优先获得 CPU 时间。

两个字符串相等的条件是（）。
- A．两个串的长度相等
- B．两个串包含的字符相等
- C．两个串的长度相等，并且两个串包含的字符相同
- D．两个串的长度相等，并且各个对应位置的字符都相等

查看答案与解析

答案：D

解析：
字符串相等的严格定义是：两个串的长度相等，且对应位置上的字符完全相同。例如 "abc" 和 "cba" 长度和包含字符相同，但不相等。

难度: ⭐
考点: #字符串 #相等定义

💡 学习锦囊

📖 相关公式与知识点:

字符串是零个或多个字符组成的有限序列。

思路分析

对比选项，只有 D 包含了“位置”这一决定性因素。

易错点

混淆“包含字符相同”与“对应位置字符相同”。

🔄 举一反三

空串和空格串是否相等？
查看练习答案与解析
答案：不相等。
解析：空串长度为 0；空格串长度大于 0（包含空格字符）。

在二维数组中，每个数组元素同时处于（）个向量中。
- A．0
- B．1
- C．2
- D．n

查看答案与解析

答案：C

解析：
在二维数组 $$A[m][n]$$ 中，任何一个元素 $$A[i][j]$$ 都既属于第 $$i$$ 行构成的行向量，又属于第 $$j$$ 列构成的列向量。因此它同时处于 2 个向量中。

难度: ⭐
考点: #数组 #多维数组

💡 学习锦囊

📖 相关公式与知识点:

二维数组可以看作是每个元素都是线性表的线性表。

思路分析

从行列的角度去理解二维平面的交叉点。

易错点

误选 n（受数组维度迷惑）。

🔄 举一反三

在三维数组中，每个元素同时处于几个向量中？
查看练习答案与解析
答案：3 个。
解析：分别属于行、列、页（三个维度）。

将递归算法转换成对应的非递归算法，除了单向递归和尾递归的情况外，通常需要使用（）保存中间结果。
- A. 链表
- B. 栈
- C. 队列
- D. 顺序表

查看答案与解析

答案：B

解析：
系统在执行递归时，本质上是利用了系统栈来保存每一层调用的返回地址和局部变量。为了手动模拟递归，最合适的数据结构就是栈。

难度: ⭐
考点: #递归转换 #栈的应用

💡 学习锦囊

📖 相关公式与知识点:

递归三要素：终止条件、递归公式、边界。

思路分析

递归的本质是后调用的先返回，这与栈的后进先出完美契合。

易错点

误选队列（队列无法实现回溯）。

🔄 举一反三

二叉树的后序遍历非递归实现需要用几个栈？
查看练习答案与解析
答案：通常需要 1 个或 2 个栈。
解析：使用双栈法最简单（一个存节点，一个存输出），单栈法需要记录上一次访问的节点。

设一棵二叉树的中序序列为 badce，后序序列为 bdeca，则该二叉树前序遍历的结果是（）。
- A. adbec
- B. decab
- C. debac
- D. abcde

查看答案与解析

答案：D

解析：

后序序列 bdeca 最后一个是 a，故根结点为 a。
中序序列为 badce，a 之前的 b 是左子树，之后的 dce 是右子树。
右子树后序为 bdec 去掉 b（左子树）得 dec，最后一个是 c，故右子树根为 c。
中序中 d 在 c 前，e 在 c 后，故 d 为 c 的左孩子，e 为 c 的右孩子。
还原出的树结构为：根 a，左 b，右 c（c 的左 d，右 e）。
前序遍历：a -> b -> c -> d -> e。

难度: ⭐⭐
考点: #二叉树还原 #遍历序列

💡 学习锦囊

📖 相关公式与知识点:

前序：根-左-右。中序：左-根-右。后序：左-右-根。
必须包含中序序列才能唯一确定一棵二叉树。

思路分析

后序找根，中序定左右，递归进行。

易错点

在确定右子树的子结构时容易推错位置。

🔄 举一反三

某二叉树的前序是 AB，中序是 BA，则后序是什么？
查看练习答案与解析
答案：BA
解析：前序 A 说明 A 是根。中序 BA 说明 B 是左孩子。后序为左-右-根，即 BA。

在 n 个结点的线索二叉树中，线索的数目是（）。
- A．n-1
- B. $$n + 1$$
- C. 2n
- D. 2n-1

查看答案与解析

答案：B

解析：
每个结点有 2 个指针域，共有 $$2n$$ 个指针域。其中， $$n$$ 个结点的二叉树共有 $$n-1$$ 条边（即用来指向孩子的有效指针）。剩余的空指针域全部用来作线索，因此线索数 = $$2n - (n-1) = n + 1$$ 。

难度: ⭐⭐
考点: #线索二叉树 #指针域

💡 学习锦囊

📖 相关公式与知识点:

二叉树分支数 = $$n - 1$$ 。
空指针数 = $$2n - (n-1) = n + 1$$ 。

思路分析

利用总体指针数减去用于表示树结构的有效指针数。

易错点

死记硬背公式容易把 $$+1$$ 记成 $$-1$$ 。

🔄 举一反三

具有 5 个结点的线索二叉树中，共有多少个线索？
查看练习答案与解析
答案：6
解析：直接代入公式 $$n+1 = 5+1 = 6$$ 。

一个有 $n$ 个顶点的无向图中边数最多有（）条。
- A．n
- B．n(n-1)
- C．n(n-1) /2
- D．2n

查看答案与解析

答案：C

解析：
无向图中，任意两个顶点之间都可以有一条边。即从 $$n$$ 个顶点中任选 2 个的组合数： $\binom{n}{2} = \frac{n(n-1)}{2}$ 。

难度: ⭐
考点: #图的性质 #最大边数

💡 学习锦囊

📖 相关公式与知识点:

无向完全图边数： $\frac{n(n-1)}{2}$ 。
有向完全图边数： $$n(n-1)$$ 。

思路分析

考查无向图达到“完全图”状态时的边数。

易错点

容易混淆无向图和有向图的公式。

🔄 举一反三

具有 5 个顶点的有向图最多有多少条边？
查看练习答案与解析
答案：20
解析：有向完全图公式 $n(n-1) = 5 \times 4 = 20$ 。

无向图的邻接矩阵是一个（）。
- A．对称矩阵
- B．零矩阵
- C．上三角矩阵
- D．对角矩阵

查看答案与解析

答案：A

解析：
在无向图中，如果顶点 $$i$$ 和顶点 $$j$$ 之间有一条边，那么 $$A[i][j] = A[j][i] = 1$$ 。因此，邻接矩阵必然是关于主对角线对称的对称矩阵。

难度: ⭐
考点: #无向图 #邻接矩阵

💡 学习锦囊

📖 相关公式与知识点:

无向图邻接矩阵第 $$i$$ 行（或列）的非零元素个数等于顶点 $$i$$ 的度。

思路分析

无向边是没有方向的，所以 $$(u, v)$$ 和 $$(v, u)$$ 等价，对应矩阵元素对称。

易错点

不要与有向图混淆。

🔄 举一反三

若无向图的邻接矩阵主对角线元素全为 0，说明什么？
查看练习答案与解析
答案：图中没有自环。
解析：主对角线元素 $$A[i][i]$$ 代表顶点到自身的边。

13．对线性表进行折半查找时，要求线性表必须（）。 - A．以顺序方式存储 - B．以链接方式存储 - C．以链接方式存储，且结点按关键码有序排序 - D．以顺序方式存储，且结点按关键码有序排序

查看答案与解析

答案：D

解析：
折半查找（二分查找）需要能够快速定位到中间元素（即随机存取），这就要求必须使用顺序存储；同时，为了能够判断目标值在前半段还是后半段，表必须是有序的。

难度: ⭐
考点: #折半查找 #前提条件

💡 学习锦囊

📖 相关公式与知识点:

折半查找平均查找长度 ASL $\approx \log_2(n+1) - 1$ 。

思路分析

折半的核心在于根据下标直接访问中间元素，链表做不到 $$O(1)$$ 访问。

易错点

误认为链表只要有序就能进行折半查找。

🔄 举一反三

链表为什么不适合用折半查找？
查看练习答案与解析
答案：链表不支持随机访问。
解析：链表找中间元素需要 $$O(n)$$ 遍历，这会使折半查找退化。

直接插入排序在最好情况下的时间代价是（）。
- A． $O ( \log _ { 2 } n )$
- B． $$O ( n )$$
- C． $O ( n \log _ { 2 } n )$
- D． $O ( n ^ { 2 } )$

查看答案与解析

答案：B

解析：
直接插入排序在原本就有序的最好情况下，每趟排序只需要与前一个元素比较一次，不需要移动元素，总共比较 $$n-1$$ 次，故时间复杂度为 $$O(n)$$ 。

难度: ⭐
考点: #直接插入排序 #时间复杂度

💡 学习锦囊

📖 相关公式与知识点:

直接插入排序平均及最坏时间复杂度： $$O(n^2)$$ 。

思路分析

记忆排序算法在不同初始状态下的性能表现。

易错点

误选 $$O(n^2)$$ （这是平均/最坏情况）。

🔄 举一反三

直接插入排序在最坏情况（逆序）下的时间复杂度是多少？
查看练习答案与解析
答案： $$O(n^2)$$
解析：每次都需要比较并移动前面所有的元素。

每次直接比较两个元素，若出现逆序排列时就交换它们的位置，此种排序方法是（）。
- A．堆排序
- B．选择排序
- C．起泡排序
- D．基数排序

查看答案与解析

答案：C

解析：
**起泡排序（冒泡排序）**的基本思想是通过相邻元素的比较与交换，使最大（或最小）的元素逐渐“浮”到表的一端。

难度: ⭐
考点: #交换排序 #起泡排序

💡 学习锦囊

📖 相关公式与知识点:

属于交换排序的还有快速排序。

思路分析

抓住关键字“交换它们的位置”。

易错点

与选择排序混淆（选择排序是每趟只在末尾交换一次）。

🔄 举一反三

快速排序的核心操作是什么？
查看练习答案与解析
答案：划分（Partition）。
解析：通过一趟排序将待排记录分割成独立的两部分。

三、填空题（每空 2 分，共 8 分）

顺序查找 n 个元素的顺序表，若查找成功，则比较关键字的次数最多为 ______ 次。

查看答案与解析

答案：n

解析：
在最坏情况下，目标元素位于顺序表的最后一个位置（第 $$n$$ 个），此时需要从头到尾比较 $$n$$ 次。

难度: ⭐
考点: #顺序查找

💡 学习锦囊

📖 相关公式与知识点:

顺序查找成功时的 ASL = $$(n+1)/2$$ 。

思路分析

考虑查找失败或在最后一个位置的极限情况。

易错点

可能误答为 $$n+1$$ （那是带哨兵且查找失败的情况）。

🔄 举一反三

顺序查找长度为 n 的顺序表，查找失败时比较了多少次？
查看练习答案与解析
答案： $$n$$ 次（或 $$n+1$$ 次，取决于实现方式是否包含哨兵）。
解析：常规遍历 $$n$$ 个都不等则失败。

一个深度为 4 的满二叉树具有 ______ 个结点。

查看答案与解析

答案：15

解析：
根据二叉树的性质，深度为 $$k$$ 的满二叉树其结点总数为 $$2^k - 1$$ 。代入 $$k=4$$ 得 $$2^4 - 1 = 16 - 1 = 15$$ 。

难度: ⭐
考点: #满二叉树

💡 学习锦囊

📖 相关公式与知识点:

深度为 $$k$$ 的满二叉树结点数 = $$2^k - 1$$ 。

思路分析

直接套用满二叉树的结点总数公式。

🔄 举一反三

深度为 4 的满二叉树第 4 层有多少个结点？
查看练习答案与解析
答案：8
解析：第 $$i$$ 层结点数公式为 $2^{i-1}$ ，代入 $$i=4$$ 得 $$2^3 = 8$$ 。

遍历二叉排序树可得到一个按关键字的有序序列。

查看答案与解析

答案：中序

解析：
二叉排序树（BST）的特点是左子树上的所有结点都小于根结点，右子树上的所有结点都大于根结点。因此，按照“左-根-右”的中序遍历顺序，可以输出一个递增的有序序列。

难度: ⭐
考点: #二叉排序树 #遍历

💡 学习锦囊

📖 相关公式与知识点:

中序遍历 BST 得到升序序列。

思路分析

记住二叉排序树的定义性质与中序遍历的契合点。

易错点

误写成前序或后序。

🔄 举一反三

如何在 BST 中查找最小值？
查看练习答案与解析
答案：从根节点出发一直往左走，直到没有左孩子。
解析：最左侧的节点即为最小值。

在顺序表（8,11,15,19,25,26,30,33,42,48,50）中，用二分（折半）法查找关键码值 19，需做的关键码比较次数为 ______ 。

查看答案与解析

答案：3

解析：
表长为 11，下标为 $0 \sim 10$ 。

第一次：low=0, high=10, mid=(0+10)/2=5，比较 a[5]=26 > 19。
第二次：low=0, high=4, mid=(0+4)/2=2，比较 a[2]=15 < 19。
第三次：low=3, high=4, mid=(3+4)/2=3，比较 a[3]=19 == 19。找到。共计比较 3 次。

难度: ⭐⭐
考点: #折半查找 #查找过程

💡 学习锦囊

📖 相关公式与知识点:

折半公式：mid = (low + high) / 2。

思路分析

严格按照二分查找的 low 和 high 指针移动过程手动模拟。

易错点

计算 mid 时向下取整的规则必须一致。

🔄 举一反三

在该表中查找 50 需要比较几次？
查看练习答案与解析
答案：4 次。
解析：
- 第一次比较 26 (mid=5)
- 第二次比较 42 (mid=8)
- 第三次比较 48 (mid=9)
- 第四次比较 50 (mid=10)

四、简答题（每小题 5 分，共 20 分）

简述深度优先搜索（DFS）和广度优先搜索（BFS）的基本思想，并分别说明它们通常借助什么数据结构来实现。

查看答案与解析

答案：

深度优先搜索（DFS）：从起始顶点出发，沿着一条路径尽可能深入，直到无法继续才回溯，尝试其他路径。通常借助栈来实现（递归本质也是系统栈）。
广度优先搜索（BFS）：从起始顶点出发，先访问所有邻接点，再按层次逐层向外扩展。通常借助队列来实现。

解析： DFS 是"一条路走到黑"，BFS 是"层层推进"。DFS 用栈是因为需要回溯（后进先出），BFS 用队列是因为需要按访问顺序逐层处理（先进先出）。

难度: ⭐⭐ 考点: #图的遍历 #DFS #BFS #栈与队列

💡 学习锦囊

📖 相关公式与知识点:

DFS 时间复杂度：邻接矩阵 $$O(n^2)$$ ，邻接表 $$O(n+e)$$
BFS 时间复杂度：邻接矩阵 $$O(n^2)$$ ，邻接表 $$O(n+e)$$

思路分析

DFS 适合路径查找、拓扑排序；BFS 适合最短路径（无权图）、层次遍历。

🔄 举一反三

在二叉树中，先序遍历对应图的哪种遍历策略？
查看练习答案与解析
答案：深度优先搜索（DFS）。解析：先序遍历是"根-左-右"，沿着左子树一直深入，回溯后再处理右子树，与 DFS 策略一致。

什么是哈希冲突？解决哈希冲突的常用方法有哪些？请至少列举两种并简要说明。

查看答案与解析

答案：

哈希冲突：不同的关键字通过哈希函数映射到了同一个哈希地址的现象。
常用解决方法：
1. 开放地址法：发生冲突时，按某种探测序列（如线性探测、平方探测）在哈希表中寻找下一个空闲位置。
2. 链地址法（拉链法）：将所有哈希地址相同的记录链接在同一个单链表中，哈希表的每个单元存放链表头指针。

解析： 哈希冲突是不可避免的（鸽巢原理），关键在于设计好的解决策略。开放地址法节省指针空间但可能产生"聚集"现象；链地址法插入删除灵活，但需要额外指针空间。

难度: ⭐⭐ 考点: #哈希表 #哈希冲突 #开放地址法 #链地址法

💡 学习锦囊

📖 相关公式与知识点:

装填因子 $\alpha = n/m$ ， $\alpha$ 越大冲突概率越高。
线性探测： $d_i = (H(key) + i) \bmod m$

易错点

开放地址法删除元素时不能直接清空，需要做"懒惰删除"标记，否则会截断探测链。

🔄 举一反三

再哈希法和建立公共溢出区也是解决冲突的方法，请简述其思想。
查看练习答案与解析
答案：
- 再哈希法：准备多个不同的哈希函数，冲突时换用下一个哈希函数计算地址。
- 公共溢出区：将冲突的记录统一存入一个独立的溢出表中。

简述二叉排序树（BST）的定义和性质。在二叉排序树上进行查找、插入和删除操作的平均时间复杂度是多少？

查看答案与解析

答案：

定义：二叉排序树或为空树，或满足以下性质的二叉树：
1. 若左子树非空，则左子树上所有结点的值均小于根结点的值；
2. 若右子树非空，则右子树上所有结点的值均大于根结点的值；
3. 左右子树本身也各是一棵二叉排序树。
平均时间复杂度：查找、插入和删除操作的平均时间复杂度均为 $O(\log_2 n)$ 。最坏情况下（树退化为单链表）为 $$O(n)$$ 。

解析： BST 的平均性能取决于树的形态是否均衡。平衡的 BST 高度约为 $\log_2 n$ ，每次操作只需沿一条路径从根走到叶子。

难度: ⭐⭐ 考点: #二叉排序树 #BST #时间复杂度

💡 学习锦囊

📖 相关公式与知识点:

中序遍历 BST 得到递增有序序列。
为克服退化问题，引入了平衡二叉树（AVL）、红黑树等。

易错点

BST 的删除操作分三种情况：叶子结点（直接删）、单分支结点（子承父业）、双分支结点（用前驱/后继替代）。

🔄 举一反三

在 BST 中查找最小值和最大值的思路分别是什么？
查看练习答案与解析
答案：
- 最小值：从根出发一直向左走，直到左孩子为空。
- 最大值：从根出发一直向右走，直到右孩子为空。

简述栈和队列的异同点，并各举一个实际应用场景。

查看答案与解析

答案：

相同点：都是操作受限的线性表，插入和删除操作都限定在端点进行。
不同点：
- 栈：仅允许在表尾（栈顶）进行插入和删除，遵循**后进先出（LIFO）**原则。
- 队列：在表尾（队尾）插入，在表头（队头）删除，遵循**先进先出（FIFO）**原则。
应用场景：
- 栈：函数调用与递归、括号匹配、表达式求值、浏览器的前进后退。
- 队列：打印机任务缓冲、操作系统进程调度、消息队列、广度优先搜索。

解析： 栈和队列是最基础的两种受限线性表，它们的区别在于元素的进出顺序不同，这决定了它们适用于不同的场景。

难度: ⭐ 考点: #栈 #队列 #线性表

💡 学习锦囊

📖 相关公式与知识点:

栈的 $$n$$ 个元素合法出栈序列数 = 卡特兰数 $C_n = \frac{1}{n+1}\binom{2n}{n}$

思路分析

判断使用栈还是队列，关键看场景是"后到先处理"还是"先到先处理"。

🔄 举一反三

双端队列（Deque）与普通队列有什么区别？
查看练习答案与解析
答案：双端队列允许在两端进行插入和删除操作，兼具栈和队列的特性，更加灵活。

五、应用题（每小题 8 分，共 16 分）

已知关键字序列 {25, 18, 46, 2, 53, 39, 67, 21}，哈希函数 H(key) = key % 7，采用链地址法解决冲突。请构造哈希表，并计算等概率下查找成功的平均查找长度 ASL。

查看答案与解析

答案：

第一步：计算各关键字的哈希地址

H(25) = 25 % 7 = 4
H(18) = 18 % 7 = 4
H(46) = 46 % 7 = 4
H(2) = 2 % 7 = 2
H(53) = 53 % 7 = 4
H(39) = 39 % 7 = 4
H(67) = 67 % 7 = 4
H(21) = 21 % 7 = 0

第二步：构造链地址哈希表

地址	链表
0	21
1	空
2	2
3	空
4	25 → 18 → 46 → 53 → 39 → 67
5	空
6	空

第三步：计算 ASLsucc

地址 0：21 比较 1 次
地址 2：2 比较 1 次
地址 4：25(1次), 18(2次), 46(3次), 53(4次), 39(5次), 67(6次)

ASL_{succ} = \frac{1 + 1 + 1 + 2 + 3 + 4 + 5 + 6}{8} = \frac{23}{8} = 2.875

解析： 本题哈希函数设计不佳，大部分关键字映射到地址 4，导致链表过长。实际应用中应选择分布更均匀的哈希函数。

难度: ⭐⭐⭐ 考点: #哈希表 #链地址法 #ASL

💡 学习锦囊

📖 相关公式与知识点:

链地址法 ASLsucc = $\frac{\sum \text{各元素在链表中的位置}}{\text{元素总数}}$
好的哈希函数应使关键字均匀分布到各地址。

易错点

链地址法中，同一链表中第 $$k$$ 个元素需要比较 $$k$$ 次才能找到。

🔄 举一反三

若改用线性探测法（表长 11），上述序列的 ASLsucc 是多少？
查看练习答案与解析
答案：约 3.25 解析：大量元素映射到地址 4，线性探测会产生严重的聚集现象，ASL 比链地址法更高。

已知一棵二叉树的前序遍历序列为 ABDEGCFH，中序遍历序列为 DBGEACHF。 (1) 画出该二叉树的结构； (2) 写出该二叉树的后序遍历序列； (3) 求该二叉树的深度。

查看答案与解析

答案：

(1) 二叉树结构：

text

(2) 后序遍历序列： D, E, B, G, F, H, C, A

(3) 树的深度： 4

解析：

第一步：确定根结点：前序第一个为 A，故 A 为根。
第二步：划分左右子树：中序 DBGE A CHF，A 左边 {D, B, G, E} 为左子树，右边 {C, H, F} 为右子树。
第三步：递归构建左子树：左子树前序 BDEG，B 为根。中序 D B GE，B 左边 D，右边 {G, E}。D 为 B 的左孩子。{G, E} 前序 EG，E 为根，中序 GE，G 在 E 左边，故 G 为 E 的左孩子，E 为 B 的右孩子。
第四步：递归构建右子树：右子树前序 CFH，C 为根。中序 C HF，C 左边无，右边 {H, F}。{H, F} 前序 FH，F 为根，中序 HF，H 在 F 左边，故 H 为 F 的左孩子，F 为 C 的右孩子。

难度: ⭐⭐⭐ 考点: #二叉树还原 #遍历序列 #树的深度

💡 学习锦囊

📖 相关公式与知识点:

前序 + 中序可唯一确定二叉树。
树的深度 = 从根到最远叶子结点的路径上的结点数。

思路分析

还原二叉树的核心：前序定根，中序定左右，递归进行。

🔄 举一反三

若已知后序序列和中序序列，如何还原二叉树？
查看练习答案与解析
答案：后序序列的最后一个元素是根结点，在中序序列中找到根后划分左右子树，递归进行。

六、算法设计题（每小题 8 分，共 16 分）

设计一个递归算法，计算二叉树中所有结点值之和。假设二叉树采用二叉链表存储，结点类型定义如下：

typedef struct node {
    int data;
    struct node *lchild, *rchild;
} BTNode;

查看答案与解析

答案：

int SumNodes(BTNode *bt) {
    if (bt == NULL) {
        return 0;
    }
    return bt->data + SumNodes(bt->lchild) + SumNodes(bt->rchild);
}

解析：

递归模型：
- 基准条件：空树结点和为 0。
- 递推关系：当前树的结点和 = 根结点值 + 左子树结点和 + 右子树结点和。
时间复杂度： $$O(n)$$ ，每个结点访问一次。
空间复杂度： $$O(h)$$ ， $$h$$ 为树的高度（递归栈深度）。

难度: ⭐⭐ 考点: #二叉树 #递归算法 #遍历

💡 学习锦囊

📖 相关公式与知识点:

二叉树递归遍历模板：处理当前结点 + 递归左子树 + 递归右子树。

思路分析

树上的递归算法通常遵循"根-左-右"的模式，将大问题分解为当前结点和左右子树三个子问题。

🔄 举一反三

设计递归算法求二叉树中所有叶子结点值之和。

查看练习答案与解析

答案：

int SumLeaf(BTNode *bt) {
    if (bt == NULL) return 0;
    if (bt->lchild == NULL && bt->rchild == NULL)
        return bt->data;
    return SumLeaf(bt->lchild) + SumLeaf(bt->rchild);
}

设计一个算法，将带头结点的单链表 L 就地逆置（不允许使用额外数组）。函数原型：void Reverse(LinkList L);

查看答案与解析

答案：

void Reverse(LinkList L) {
    if (L == NULL || L->next == NULL) {
        return;
    }
    LNode *p = L->next;
    LNode *q;
    L->next = NULL;
    while (p != NULL) {
        q = p->next;
        p->next = L->next;
        L->next = p;
        p = q;
    }
}

解析：

算法思想：采用头插法。从头到尾遍历原链表，将每个结点依次摘下，插入到头结点之后。
执行过程：
1. 保存头结点后的第一个结点 p，将头结点与后续断开（L->next = NULL）。
2. 循环：保存 p 的后继 q，将 p 用头插法插入 L 之后，p 移动到 q。
3. 循环结束后，链表完成逆置。
时间复杂度： $$O(n)$$
空间复杂度： $$O(1)$$ （就地逆置）

难度: ⭐⭐⭐ 考点: #单链表 #链表逆置 #头插法

💡 学习锦囊

📖 相关公式与知识点:

头插法：p->next = L->next; L->next = p;
链表操作核心：修改指针前先保存后继结点，防止链表断裂。

易错点

必须先用 q 保存 p->next，再修改 p->next，否则会丢失后续结点。

🔄 举一反三

如何判断一个单链表是否有环？
查看练习答案与解析
答案：使用快慢指针（Floyd 判圈法）。快指针每次走两步，慢指针每次走一步，若相遇则有环；若快指针走到 NULL 则无环。

:::::

空串的长度为 ______。

查看答案与解析

答案：0

解析：
空串是指不包含任何字符的字符串，其长度为零。记作 $$S = ""$$ 。

难度: ⭐
考点: #字符串

💡 学习锦囊

📖 相关公式与知识点:

串长：串中包含字符的个数。

思路分析

不要混淆空串与空格串。

易错点

误认为空格串长度也是 0。

🔄 举一反三

字符串 " " 的长度是多少？
查看练习答案与解析
答案：1
解析：包含一个空格字符。

四、结构问答题（每题 10分，共 40 分）

某通信电文由 A、B、C、D、E、F 六个字符组成，它们在电文中出现的次数分别是 16，5，9，3，20，1。
①、试画出其赫夫曼树。（6分）
②、确定其对应的赫夫曼编码。（4 分）

查看答案与解析

答案：

① 构造的赫夫曼树如下（采用 ASCII 图示表示）：

text

          [54]
         /    \
      E(20)   [34]
             /    \
          A(16)   [18]
                 /    \
               [9]    C(9)
              /   \
            [4]   B(5)
           /   \
         F(1)  D(3)

② 各个字符对应的赫夫曼编码为（规定左分支为 0，右分支为 1）：

A：10
B：1101
C：111
D：11001
E：0
F：11000

解析：

第一步：排序权重：F(1), D(3), B(5), C(9), A(16), E(20)。
第二步：取最小的 F(1) 和 D(3) 合并为 4。
第三步：取最小的 4 和 B(5) 合并为 9。
第四步：取最小的 9 和 C(9) 合并为 18。
第五步：取最小的 A(16) 和 18 合并为 34。
第六步：最后合并 34 和 E(20) 为 54。

难度: ⭐⭐
考点: #赫夫曼树 #赫夫曼编码

💡 学习锦囊

📖 相关公式与知识点:

WPL（带权路径长度）= $\sum w_i l_i$ 。

思路分析

每次挑选当前未合并的节点中权值最小的两个。

🔄 举一反三

权值分别为 {2, 3, 4, 7} 的赫夫曼树 WPL 是多少？
查看练习答案与解析
答案：30
解析：
- 第一步：构造赫夫曼树。每次选取权值最小的两个节点合并。
  - 合并 2 和 3，得到新节点 5。
  - 合并 5 和 4，得到新节点 9。
  - 合并 9 和 7，得到根节点 16。
- 第二步：计算 WPL。
  - 节点 7 的路径长度为 1。
  - 节点 4 的路径长度为 2。
  - 节点 2 和 3 的路径长度为 3。
  - WPL = $7 \times 1 + 4 \times 2 + 2 \times 3 + 3 \times 3 = 7 + 8 + 6 + 9 = 30$ 。

图 1 表示一个地区的交通网，顶点表示城市，边表示连接城市间的公路，边上的权表示修建公路花费的代价。怎样选择能够沟通每个城市且总造价最省的 $$n - 1$$ 条公路，画出所有可能的方案。

查看答案与解析

答案：

本题是求解最小生成树问题。利用 Prim 或 Kruskal 算法，由于网中有两条权值为 6 的边，可以得到以下两种等代价方案（总造价均为 33）。

::: note 重要提示由于历史答卷资源限制，方案图示暂时缺失。建议同学们根据图 1 亲自动手绘制：

方案一：依次选取权值为 1, 2, 3, 4, 5, 6(a), 7... 的边，注意不构成环。
方案二：在遇到权值相等的边时，选择另一条不构成环的等权边进行替换。 :::

方案一：

方案二：

难度: ⭐⭐⭐
考点: #最小生成树 #Prim #Kruskal

💡 学习锦囊

📖 相关公式与知识点:

最小生成树的边数等于顶点数减一（ $$n-1$$ ）。

思路分析

推荐使用 Kruskal（按边权从小到大选择且不构成环）。

🔄 举一反三

当图中各边权值互不相等时，最小生成树是否唯一？
查看练习答案与解析
答案：唯一。
解析：没有冲突的选择。

设哈希(Hash)表的地址范围为 $0 \sim 15$ ，哈希函数为： $H(K)=K \pmod{16}$ ，K 为关键字，用线性探测再散列法处理冲突，输入关键字序列: $$(10，24，32，17，31，30，46，47，40，63，49)$$ 构造哈希表，试回答下列问题。 ①、画出哈希表示意图；（4分） ②、若查找关键字 63,需要依次与哪些关键字比较;（2分） ③、若查找关键字 40,需要依次与哪些关键字比较;（2分） ④、假定每个关键字的查找概率相等,求查找成功时的平均查找长度。（2分）

查看答案与解析

答案：

① 哈希表示意图为：

地址	0	1	2	3	4	5	6	7	8	9	10	11	12	13	14	15
关键字	32	17	46	47	63	49			24	40	10				30	31

② 查找 63 依次比较的关键字：31, 32, 17, 46, 47, 63

③ 查找 40 依次比较的关键字：24, 40

④ 平均查找长度 ASL = $\frac{1+1+1+1+1+1+5+5+2+6+5}{11} = \frac{29}{11}$

难度: ⭐⭐⭐
考点: #哈希表 #线性探测 #ASL

💡 学习锦囊

📖 相关公式与知识点:

线性探测： $d_i = (H(K) + i) \pmod m$ 。

思路分析

冲突时顺延向后寻找空位，注意循环回绕。

🔄 举一反三

设哈希表长为 11，哈希函数 $H(K) = K \pmod{11}$。采用线性探测法处理冲突，将关键字序列 $(1, 12, 23, 34)$ 依次插入，关键字 34 的存储地址是多少？
查看练习答案与解析
答案：4
解析：
- $1 \pmod{11} = 1$ ，存入地址 1。
- $12 \pmod{11} = 1$ ，冲突，向后探测到地址 2 为空，存入 2。
- $23 \pmod{11} = 1$ ，冲突，探测地址 2（占）、3（空），存入 3。
- $34 \pmod{11} = 1$ ，冲突，探测地址 2（占）、3（占）、4（空），存入 4。

设要将序列 $$(12,5,9,20,6,31,24)$$ 中的关键字按升序排列,试写出下列结果。 ①、起泡排序第一趟排序的结果:（4分） ②、增量为 4 的希尔排序第一趟排序的结果:（3分） ③、二路归并排序第一趟排序的结果:（3分）

查看答案与解析

答案：

① 起泡排序第一趟： $$(5, 9, 12, 6, 20, 24, 31)$$
② 增量为 4 的希尔排序第一趟： $$(6, 5, 9, 20, 12, 31, 24)$$
③ 二路归并排序第一趟： $$(5, 12, 9, 20, 6, 31, 24)$$

难度: ⭐⭐
考点: #排序过程 #起泡排序 #希尔排序 #归并排序

💡 学习锦囊

📖 相关公式与知识点:

希尔排序：基于跨步长子序列的插入排序。

思路分析

模拟每种排序算法的单趟核心操作。

🔄 举一反三

快速排序以 12 为基准的第一趟划分结果？
查看练习答案与解析
答案： $$(6, 5, 9, 12, 20, 31, 24)$$
解析：小于 12 的放左边，大于的放右边。

五、用类 C 语言描述下列算法，并给出必要说明（10分）。

已知两个无序单链表，均为带有链表头结点的链表，现需将这两个无序单链表进行排序变为有序链表，然后再将这两个链表合并为一个链表。请按照以下提示和要求给出算法。
已知链表存储结构为：
c
```
typedef struct Node {
    int data;
    struct Node *next;
} Linknode, *Link;
```
1
2
3
4
（1）对单链表中元素按插入方法排序的 C 语言描述算法如下，其中 L 为链表头结点指针。请填充算法中标出的空白处，完成其功能。（3分）
c
```
void Insertsort(Link &L) {
    Link p, q, r, u;
    p = L->next;
    L->next = NULL;
    while (p != NULL) {
        r = L;
        q = L->next;
        while (① && q->data <= p->data) {
            r = q;
            q = q->next;
        }
        u = p->next;
        ②;
        ③;
        p = u;
    }
}
```
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
（2）请给出有序单链表的合并算法及其算法的时间复杂度（7分）

查看答案与解析

答案：

（1）空白处内容：

① q != NULL
② p->next = r->next（或 p->next = q）
③ r->next = p

（2）合并算法及复杂度：

void MergeList_L(Link &La, Link &Lb, Link &Lc) {
    Link pa = La->next; 
    Link pb = Lb->next;
    Lc = La; // 复用 La 的头结点作为 Lc 的头结点
    Link pc = Lc;
    
    while (pa && pb) {
        if (pa->data <= pb->data) {
            pc->next = pa;
            pc = pa;
            pa = pa->next;
        } else {
            pc->next = pb;
            pc = pb;
            pb = pb->next;
        }
    }
    // 插入剩余段
    pc->next = pa ? pa : pb; 
    free(Lb); // 释放 Lb 的头结点
}

时间复杂度： $O(\text{ListLength}(La) + \text{ListLength}(Lb))$

难度: ⭐⭐⭐
考点: #链表排序 #链表合并 #算法填空

💡 学习锦囊

📖 相关公式与知识点:

尾插法合并。

思路分析

指针穿针引线，注意不断链。

易错点

合并后不要忘记释放多余的头结点指针。

🔄 举一反三

如何实现空间复杂度为 O(1) 的逆序合并？
查看练习答案与解析
答案：使用头插法。
解析：比较大小后，将元素插到新链表的头部。

《数据结构》第一学期期末试卷A (精选01) ​

一、判断题（每题 2 分，共 10 分）（正确的打"√"，错误的打"×"。） ​

二、单选题（每题 2 分，共 30 分） ​

三、填空题（每空 2 分，共 8 分） ​

四、简答题（每小题 5 分，共 20 分） ​

五、应用题（每小题 8 分，共 16 分） ​

六、算法设计题（每小题 8 分，共 16 分） ​

四、结构问答题（每题 10分，共 40 分） ​

五、用类 C 语言描述下列算法，并给出必要说明（10分）。 ​

《数据结构》第一学期期末试卷A (精选01)

一、判断题（每题 2 分，共 10 分）（正确的打"√"，错误的打"×"。）

二、单选题（每题 2 分，共 30 分）

三、填空题（每空 2 分，共 8 分）

四、简答题（每小题 5 分，共 20 分）

五、应用题（每小题 8 分，共 16 分）

六、算法设计题（每小题 8 分，共 16 分）

四、结构问答题（每题 10分，共 40 分）

五、用类 C 语言描述下列算法，并给出必要说明（10分）。